package com.njupt.Tree;



import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/11/25 10:27
 * @Description: 101.对称树
 * @Version: 1.0
 */


public class IsSymmetric {

    public boolean isSymmetric(TreeNode root) {
        if(root == null
                || (root.left == null && root.right == null)) return true;
        TreeNode leftCur = root.left;
        TreeNode rightCur = root.right;
        Deque<TreeNode> stackLeft = new LinkedList<>();
        Deque<TreeNode> stackRight = new LinkedList<>();
        stackLeft.push(leftCur);
        stackRight.push(rightCur);
        while( (!stackLeft.isEmpty() && !stackRight.isEmpty()) ){
            leftCur = stackLeft.pop();
            rightCur = stackRight.pop();
            if(leftCur== null && rightCur ==null){
                continue;
            }

            if((leftCur==null && rightCur != null)
                    || (leftCur!=null && rightCur == null)
                    || leftCur.val != rightCur.val){
                return false;
            }
             stackLeft.push(leftCur.right);
             stackLeft.push(leftCur.left);

             stackRight.push(rightCur.left);
             stackRight.push(rightCur.right);
        }
        return true;
    }

    public boolean isSymmetric1(TreeNode root) {
        if(root == null
                || (root.left == null && root.right == null)) return true;

        TreeNode leftCur = root.left;
        TreeNode rightCur = root.right;
        Deque<TreeNode> leftStack  = new LinkedList<>();
        Deque<TreeNode> rightStack = new LinkedList<>();

        while((leftCur != null || !leftStack.isEmpty())
                || (rightCur != null || !rightStack.isEmpty())){
            if(leftCur != null && rightCur != null){
                if(leftCur.val != rightCur.val){
                    return false;
                }
                leftStack.push(leftCur);
                rightStack.push(rightCur);
                leftCur = leftCur.left;
                rightCur = rightCur.right;
            }else if( (leftCur == null && rightCur != null)
                    || (leftCur != null && rightCur == null)){
                return false;
            }else {
                leftCur = leftStack.pop();
                leftCur = leftCur.right;

                rightCur = rightStack.pop();
                rightCur = rightCur.left;
            }
        }
        return true;
    }

    public boolean isSymmetric2(TreeNode root) {
        if(root == null) return true;
        return compare(root.left,root.right);
    }

    public Boolean compare(TreeNode left,TreeNode right){
        if((left== null && right !=null) || (left != null && right == null)){
            return false;
        }else if(left == null && right==null){
            return true;
        }else if(left.val != right.val){
            return false;
        }
        Boolean outSide = compare(left.left, right.right);
        Boolean inside = compare(left.right, right.left);
        return outSide && inside;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(3);


//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(2);
//        root.left.right = new TreeNode(3);
//        root.right.right = new TreeNode(3);
        IsSymmetric test = new IsSymmetric();
        System.out.println(test.isSymmetric2(root));
    }
}
